package com.example.demo.suanfa_jiegou;

import java.util.Stack;

/**
 * @program: java_base
 * @description: 使用栈结构，实现队列功能
 * @author: zhouhongtao
 * @happyCreateTime: 2022/03/07 16:27
 */
public class QueueUseStackDemo {
    /**
     * 经典面试题：要求使用栈结构，实现树的宽度优先遍历。
     * <p>
     * 要实现队列功能，需要使用栈结构实现。
     * 实现思路：可以使用 两个栈结构，栈1=pushStack 栈2=popStack
     * 原则：
     * push动作要求 popStack 栈必须为空
     * pop动作要求 pushStack 栈必须为空
     * <p>
     * 细节：
     * 从push函数，向pushStack放入数据，前需要校验popStack
     * 从pop函数， 从popStack弹出数据，前需要向pushStack校验是否为空
     */

    public static class TwoStacksQueue {

        private Stack<Integer> pushStack;
        private Stack<Integer> popStack;

        public TwoStacksQueue() {
            pushStack = new Stack<>();
            popStack = new Stack<>();
        }

        private void push2Pop() {
            while (!pushStack.isEmpty()) {
                popStack.add(pushStack.pop());
            }
        }

        private void pop2Push() {
            while (!popStack.isEmpty()) {
                pushStack.add(popStack.pop());
            }
        }

        public void push(int value) {
            pop2Push();
            pushStack.add(value);
        }

        public int pop() {
            push2Pop();
            return popStack.pop();
        }


    }

}
